그뢰브너 기저

3. 역사

브루노 부흐베르거(Bruno Buchberger)가 1965년에 박사 학위 논문에서 그뢰브너 기저를 정의하고, 이를 계산하는 알고리즘을 발표하였다.^[14][15] "그뢰브너 기저"라는 이름은 부흐베르거의 박사 과정 지도 교수 볼프강 그뢰브너(Wolfgang Gröbner)의 이름을 딴 것이다.

1964년에는 국소환에서의 유사한 이론이 히로나카 헤이스케에 의해 발견되었으며, '''표준 기저''' (''standard basis^영어'' 또는 ''Hironaka's standard basis^영어'')라고도 불린다. 자유 리 대수의 틀 내에서의 유사한 이론은 A. I. 시르쇼프에 의해 1962년에 발견되었지만, 소련 밖에서는 널리 알려지지 않았다.

4. 성질

다음에서 명시적으로 언급하지 않는 한, 아래에 나오는 모든 결과는 임의의 단항 순서에 대해 유효하다.^[3] 사전식 순서는 계산하기 가장 어려운 순서 중 하나이며, 가중 역 사전식 순서(grevlex)나 소거 순서(lexdeg)를 사용하는 것이 더 효율적이다.

환원된 그뢰브너 기저는 주어진 아이디얼과 단항식 순서에 대해 ''유일''하다. 따라서 두 아이디얼이 동일할 필요충분조건은 두 아이디얼이 동일한 (환원된) 그뢰브너 기저를 갖는 것이다.

다항식 환 ''R''에서의 아이디얼 ''I''의 '''차원'''은 환 ''R''/''I''의 크룰 차원이며, ''I''의 영점의 대수적 다양체의 차원과 같다. 이는 대수적 집합과 교차하기 위해 필요한 일반 위치에 있는 초평면의 수와 같으며, 유한 개의 점이다. 아이디얼과 관련 대수적 집합의 '''차수'''는 이 유한한 교점의 점의 개수이며, 중복도를 고려하여 계산된다. 특히 초곡면의 차수는 정의 다항식의 차수와 같다.

차수와 차원 모두 임의의 단항식 순서에 대한 아이디얼의 그뢰브너 기저의 선도 단항식 집합에만 의존한다. 차원은 선도 단항식이 ''S''의 변수에만 의존하지 않도록 하는 변수 집합 ''S''의 최대 크기이다. 아이디얼의 차원이 0이면, 각 변수 ''x''에 대해 그뢰브너 기저에는 ''x''의 거듭제곱인 선도 단항식이 있다.

차원과 차수는 아이디얼의 힐베르트 급수에서 추론할 수 있는데, 이는 $\backslash sum\_\{i=0\}^\backslash infty\; d\_i\; t^i$ 형태의 급수이며, 여기서 $d\_i$는 그뢰브너 기저의 선도 단항식의 배수가 아닌 차수 ''i''의 단항식의 개수이다. 힐베르트 급수는 다음과 같은 유리 분수로 합산될 수 있다.

:$\backslash sum\_\{i=0\}^\backslash infty\; d\_it^i=\backslash frac\{P(t)\}\{(1-t)^d\},$

여기서 ''d''는 아이디얼의 차원이고 $P(t)$는 $P(1)$이 아이디얼의 차수인 다항식이다.

차원과 차수는 단항식 순서의 선택에 의존하지 않지만, 단항식 순서를 변경하면 힐베르트 급수와 다항식 $P(t)$가 변경된다.

그뢰브너 기저를 계산하는 기능을 제공하는 대부분의 컴퓨터 대수 시스템은 힐베르트 급수를 계산하는 기능, 그리고 차원과 차수를 계산하는 기능도 제공한다.

4. 1. 동치 조건

4. 2. 유일성

5. 기본 연산

5. 1. 선두 항, 계수, 단항식

5. 2. 다항식 연산

• 두 다항식의 덧셈은 두 다항식의 해당 항 목록을 병합하는 방식으로 이루어진다. 만약 동일한 단항식이 두 다항식에 모두 나타나는 경우에는 별도의 처리가 필요하다.
• 다항식에 스칼라를 곱하는 것은 각 항의 계수에 해당 스칼라를 곱하는 것으로, 표현에 다른 변경은 없다.
• 다항식에 단항식 ''m''을 곱하는 것은 다항식의 각 단항식에 ''m''을 곱하는 것이다. 이는 단항식 순서의 정의에 따라 항 순서를 변경하지 않는다.

5. 3. 단항식의 나누어떨어짐

5. 4. 환원(Reduction)

• 사전식 순서 (lex)
• 차수 사전식 순서 (grlex)
• 차수 역 사전식 순서 (grevlex)

• ''g''가 ''F''의 어떤 요소 ''f''로 ''h''로 간약화되는 것을

• ''g''가 ''F''의 어떤 요소 ''f''에 의한 간약화의 유한한 단계에서 ''h''로 간약화되는 것을

5. 4. 1. 환원의 비유일성

5. 5. S-다항식 (S-polynomial)

6. 계산 알고리즘

부흐베르거 알고리즘은 그뢰브너 기저를 계산하는 가장 오래된 알고리즘이다. 이는 브루노 부흐베르거가 그뢰브너 기저 이론과 함께 고안했다. 구현하기는 간단하지만, 초기 구현은 사소한 문제만 해결할 수 있다는 것이 곧 드러났다. 주요 문제는 다음과 같다.

# 결과적인 그뢰브너 기저가 작더라도 중간 다항식은 엄청나게 클 수 있다. 그 결과, 대부분의 계산 시간이 메모리 관리에 소요될 수 있다. 따라서, 전문화된 메모리 관리 알고리즘이 효율적인 구현의 근본적인 부분이 될 수 있다.

# 계산 중에 발생하는 정수가 빠른 곱셈 알고리즘과 다중 모듈러 산술을 사용하기에 충분히 클 수 있다. 이러한 이유로, 대부분의 최적화된 구현은 GMPlibrary를 사용한다. 또한, 모듈러 산술, 중국인의 나머지 정리, 헨젤 리프팅이 최적화된 구현에 사용된다.

# 줄여야 할 S-다항식과 이를 줄이는 데 사용되는 다항식의 선택은 휴리스틱에 달려 있다. 많은 계산 문제에서와 마찬가지로, 휴리스틱은 대부분의 숨겨진 단순화를 감지할 수 없으며, 휴리스틱 선택을 피하면 알고리즘 효율성이 극적으로 향상될 수 있다.

# 대부분의 경우 계산된 대부분의 S-다항식은 0으로 줄어든다. 즉, 대부분의 계산 시간이 0을 계산하는 데 소요된다.

# 응용 분야에 가장 자주 필요한 단항식 순서 (순수 사전식)는 일반적으로 가장 쉬운 계산으로 이어지는 순서가 아니며, 일반적으로 ''degrevlex'' 순서이다.

3번 문제를 해결하기 위해 장-샤를 포제르가 F4 및 F5 알고리즘을 도입하기 전에 많은 개선 사항, 변형 및 휴리스틱이 제안되었다. 이러한 알고리즘은 정수 계수 또는 소수 모듈로 정수의 계수를 위해 설계되었으므로, 부흐베르거 알고리즘은 더 일반적인 계수에 유용하게 남아 있다.

6. 1. 부흐베르거 알고리즘

• G를 F로 초기화한다.
• G에 속하는 임의의 다항식 쌍 f1, f2에 대해, S-다항식을 G로 축약하여 h를 구한다.
• h ≠ 0 이면 G에 h를 추가하고 반복한다.
• h = 0 이면 다음 쌍을 처리한다.

6. 2. F4 및 F5 알고리즘

6. 3. 기저 변환 알고리즘

7. 응용

다음은 명시적으로 언급하지 않는 한^[3], 아래에 나오는 모든 결과는 임의의 단항 순서에 대해 유효하다(아래 언급된 다양한 순서의 정의는 해당 문서를 참조).

환원된 그뢰브너 기저는 주어진 아이디얼과 단항식 순서에 대해 ''유일''하다. 따라서 두 아이디얼이 동일할 필요충분조건은 두 아이디얼이 동일한 (환원된) 그뢰브너 기저를 갖는 것이다 (일반적으로 그뢰브너 기저 소프트웨어는 항상 환원된 그뢰브너 기저를 생성한다).

== 아이디얼 멤버십 문제 ==

이상 ''I''의 환원에 의해 다항식 ''f''가 그뢰브너 기저 ''G''로 환원되면 ''f''가 ''I''에 포함될 때만 0이 된다. 이를 통해 이상 내의 원소의 소속 여부를 테스트할 수 있다. 또 다른 방법은 ''G''∪{''f''}의 그뢰브너 기저가 ''G''와 같은지 확인하는 것이다.

''f''₁, ..., ''f''_''k''에 의해 생성된 이상 ''I''가 이상 ''J''에 포함되는지 테스트하려면, 모든 f/f^영어_I/I^영어가 ''J''에 속하는지 테스트하면 된다. 또한 ''J''와 J/J^영어 ∪ {''f''₁, ...,''f''_''k''}의 환원된 그뢰브너 기저의 동일성을 테스트할 수도 있다.

== 다항식 방정식계 풀이 ==

모든 다항식 집합은 다항식을 0으로 설정하여 다항식 방정식계로 볼 수 있다.^[13] 이러한 시스템의 해 집합은 생성된 아이디얼에만 의존하며, 따라서 주어진 생성 집합이 생성된 아이디얼의 그뢰브너 기저(모든 순서)로 대체되어도 변경되지 않는다. 다항식의 계수를 포함하는 대수적으로 닫힌 체의 좌표를 가진 이러한 해를 ''아이디얼의 영점''이라고 한다. 유리수 계수의 일반적인 경우, 이 대수적으로 닫힌 체는 복소수 체로 선택된다.^[13]

1이 아이디얼에 속하는 경우(힐베르트 영점 정리) 또는 그뢰브너 기저(모든 단항식 순서에 대해)에 1이 포함된 경우, 또는 해당 축소된 그뢰브너 기저가 [1]인 경우에만 아이디얼은 영점을 갖지 않는다(방정식 시스템은 모순 방정식이다).^[13]

아이디얼 ''I''의 그뢰브너 기저 ''G''가 주어지면, 각 변수 ''x''에 대해 ''G''가 선도 단항식이 ''x''의 거듭제곱인 다항식(선도 항에 다른 변수가 나타나지 않음)을 포함하는 경우에만 유한 개의 영점을 갖는다. 이러한 경우, 중복도를 포함하여 계산된 영점의 수는 ''G''의 모든 선도 단항식의 배수가 아닌 단항식의 수와 같다. 이 수는 아이디얼의 ''차수''라고 한다.^[13]

영점의 수가 유한할 때, 사전식 단항식 순서에 대한 그뢰브너 기저는 이론적으로 해를 제공한다. 해의 첫 번째 좌표는 첫 번째 변수에만 의존하는 기저의 다항식의 다항식 최대공약수의 근이다. 이 근을 기저에 대입한 후, 이 해의 두 번째 좌표는 두 번째 변수에만 의존하는 결과 다항식의 최대공약수의 근이 되는 식이다. 이러한 해결 과정은 GCD 계산과 근사 계수를 가진 다항식의 근 찾기를 포함하므로 수치적 불안정성 때문에 실용적이지 않으므로 이론적일 뿐이다.^[13] 따라서 그뢰브너 기저를 통해 다항식 시스템을 해결하기 위해 다른 방법이 개발되었다.^[13]

예를 들어 수식 처리 시스템(GAP)에서는 유리수체 위의 2변수 다항식환 '''Q'''[''x'', ''y'']에서의 아이디얼 ⟨''x''³ − 3''x''² − ''y'' + 1, −''x''² + ''y''² − 1⟩의 약 그뢰브너 기저는 다음과 같이 계산된다.^[13] 이 계산에 의해 해의 ''y'' 좌표 값은 ''x''에 의존하지 않는 대수 방정식 ''y''⁵ + ''y''⁴ − 11''y''³ − 17''y''² + 9''y'' + 17 = 0의 근으로 계산할 수 있다. ''x'' 좌표 값은 나머지 방정식에 얻어진 ''y'' 좌표 값을 대입하면 얻을 수 있다.^[13]

== 소거 이론 (Elimination Theory) ==

그뢰브너 기저를 "제거" 단항식 순서로 계산하면 계산적인 제거 이론이 가능하다. 이는 변수를 두 하위 집합 ''X''와 ''Y''로 나눈 다항식 환 $K[x\_1,\backslash ldots,x\_n,y\_1,\backslash ldots,y\_m]=K[X,Y]$을 고려하여, ''X''를 "제거"하는 제거 단항식 순서를 선택하는 것에 기반한다. 즉, 두 단항식을 먼저 ''X'' 부분을 비교하고 동일한 경우에만 ''Y'' 부분을 고려하여 비교하는 단항식 순서를 사용한다. 이는 ''X'' 변수를 포함하는 단항식이 ''X''에 독립적인 모든 단항식보다 크다는 것을 의미한다.

만약 ''G''가 이 단항식 순서에 대한 아이디얼 ''I''의 그뢰브너 기저이면, $G\backslash cap\; K[Y]$는 $I\backslash cap\; K[Y]$의 그뢰브너 기저이다 (이 아이디얼은 종종 "제거 아이디얼"이라고 불린다). 또한, $G\backslash cap\; K[Y]$는 ''G''의 최고차 항이 ''K''[''Y'']에 속하는 다항식으로 정확히 구성된다.

이 "제거 속성"은 여러 응용 분야를 가지고 있다. 대수 기하학에서 "제거"는 아핀 대수 집합을 주변 공간의 부분 공간으로 사영하는 기하학적 연산을 실현한다. 아이디얼 ''I''로 정의된 대수 집합의 ''Y''-부분 공간으로의 사영의 (자리스키 닫힘)은 아이디얼 $I\backslash cap\; K[Y]$에 의해 정의된다.

$x\_1>\backslash cdots\; >x\_n$인 사전식 순서는 모든 분할 $\backslash \{x\_1,\; \backslash ldots,\; x\_k\backslash \},\backslash \{x\_\{k+1\},\backslash ldots,x\_n\backslash \}$에 대한 제거 순서이다. 따라서 이 순서에 대한 그뢰브너 기저는 일반적으로 필요한 것보다 훨씬 더 많은 정보를 담고 있으며, 이것이 사전식 순서에 대한 그뢰브너 기저가 일반적으로 계산하기 가장 어려운 이유를 설명할 수 있다.

== 아이디얼의 교집합 ==

그뢰브너 기저를 사용하여 두 아이디얼의 교집합을 계산할 수 있다. ''f''₁, ..., ''f''_''m''로 생성되는 아이디얼 ''I''와 ''g''₁, ..., ''g''_''k''로 생성되는 아이디얼 ''J''가 주어졌을 때, 교집합 ''I'' ∩ ''J''의 그뢰브너 기저를 얻을 수 있다. 새로운 변수 ''t''를 도입하고, 첫 번째 블록은 ''t''만을, 다른 블록은 나머지 변수들을 포함하는 소거 순서를 사용한다. 즉, ''t''를 포함하는 단항식이 ''t''를 포함하지 않는 모든 단항식보다 크도록 설정한다. 이 순서를 사용하여 아이디얼 $K=\backslash langle\; tf\_1,\backslash ldots,\; tf\_m,\; (1-t)g\_1,\; \backslash ldots,\; (1-t)g\_k\backslash rangle$의 그뢰브너 기저를 계산한다. ''I'' ∩ ''J''의 그뢰브너 기저는 이 그뢰브너 기저에서 ''t''를 포함하지 않는 다항식들로 구성된다.

이는 아이디얼 ''K''가 $(a-b)t+b$ 형태의 다항식 ($a\backslash in\; I$, $b\backslash in\; J$)으로 구성되어 있다는 사실을 통해 증명할 수 있다. 이 다항식이 ''t''에 의존하지 않으려면 $a=b$여야 하고, 이는 $b\backslash in\; I\backslash cap\; J$를 의미한다.

== 유리 곡선의 음함수화 (Implicitization) ==

유리 곡선은 다음과 같은 형태의 매개변수 방정식을 갖는 대수 곡선이다.

:$\backslash begin\{align\}$

x_1 &= \frac{f_1(t)}{g_1(t)}\\

&\;\;\vdots\\

x_n &= \frac{f_n(t)}{g_n(t)},

\end{align}



여기서 $f\_i(t)$와 $g\_i(t)$는 1 ≤ ''i'' ≤ ''n''에 대해 일변수 다항식이다. $f\_i(t)$와 $g\_i(t)$가 서로소라고 가정할 수 있다.

음함수화는 그러한 곡선의 음함수를 계산하는 것이다. ''n'' = 2, 즉 평면 곡선의 경우, 이는 결합자를 사용하여 계산할 수 있다. 음함수는 다음과 같은 결합자이다.

:$\backslash text\{Res\}\_t(g\_1x\_1-f\_1,g\_2x\_2-f\_2).$

그뢰브너 기저를 사용한 소거는 $\backslash langle\; g\_1x\_1-f\_1,\backslash ldots,\; g\_nx\_n-f\_n\backslash rangle$의 아이디얼에서 ''t''를 소거함으로써 모든 값의 ''n''에 대해 음함수화를 가능하게 한다. ''n'' = 2인 경우, 맵 $t\; \backslash mapsto\; (x\_1,x\_2)$가 거의 모든 ''t''에 대해 단사 함수이면 결과는 결합자와 동일하다. 그렇지 않은 경우, 결합자는 소거 결과의 거듭제곱이다.

== 포화 (Saturation) ==

다항식 방정식으로 문제를 모델링할 때, 퇴화된 경우를 피하기 위해 일부 수량이 0이 아니라고 가정하는 경우가 많다. 예를 들어, 삼각형이 선분으로 퇴화되는 경우, 즉 한 변의 길이가 다른 변들의 길이의 합과 같아지는 경우 많은 속성이 거짓이 된다. 이러한 상황에서는 퇴화된 해를 무시하지 않으면 다항식 시스템에서 관련 정보를 추론할 수 없다. 보다 정확하게는, 방정식 시스템은 여러 개의 기약 성분을 가질 수 있는 대수적 집합을 정의하며, 퇴화 조건이 모든 곳에서 0인 성분을 제거해야 한다.

이것은 퇴화 조건으로 방정식을 ''포화''시켜 수행하며, 이는 그뢰브너 기저의 소거 속성을 통해 수행할 수 있다. 환의 국소화는 몇몇 원소들의 형식적 역원을 그것에 추가하는 것으로 이루어진다.

환 ''R''의 아이디얼 ''I''에 대한 ''f''에 대한 '''포화'''는 ''R''에서 $R\_f$로의 정규 사상 하에서 $R\_f\; I$의 역상이다. 그것은 $I:f^\backslash infty=\; \backslash \{g\backslash in\; R\; \backslash mid\; (\backslash exists\; k\backslash in\; \backslash mathbb\; N)\; f^k\; g\backslash in\; I\backslash \}$이며, ''f''의 거듭제곱과 곱한 것이 ''I''에 속하는 ''R''의 모든 원소로 구성된 아이디얼이다.

만약 ''J''가 ''I''와 1−''ft''에 의해 ''R''[''t'']에서 생성된 아이디얼이라면, $I:f^\backslash infty\; =\; J\backslash cap\; R$이다. 따라서, 만약 ''R''이 다항식 환이라면, ''t''를 제거하는 그뢰브너 기저 계산은 다항식에 의한 아이디얼의 포화의 그뢰브너 기저를 생성한다.

포화의 중요한 속성은, 그것이 아이디얼 ''I''에 의해 정의된 대수적 집합에서 다항식 ''f''가 0인 기약 성분을 제거하도록 보장하는 것이다. ''$I:f^\backslash infty$의 소수 분해는 I의 소수 분해의 구성 요소로, f의 어떤 거듭제곱도 포함하지 않는다.''

유한한 다항식 집합 ''F''에 의해 생성된 다항식 아이디얼의 ''f''에 대한 포화의 그뢰브너 기저는 $F\backslash cup\backslash \{1-tf\backslash \}$에서 ''t''를 제거함으로써, 즉 제거 순서에 따라 $F\backslash cup\backslash \{1-tf\backslash \}$의 그뢰브너 기저에서 ''t''에 의존하지 않는 다항식을 유지함으로써 얻을 수 있다.

''F''를 사용하는 대신, ''F''의 그뢰브너 기저에서 시작할 수도 있다. 어떤 방법이 가장 효율적인지는 문제에 따라 다르다. 그러나 포화가 어떤 성분도 제거하지 않는다면, 즉 아이디얼이 포화된 아이디얼과 같다면, 먼저 ''F''의 그뢰브너 기저를 계산하는 것이 보통 더 빠르다. 반면에, 포화가 일부 성분을 제거한다면, 직접 계산이 극적으로 더 빠를 수 있다.

만약 여러 다항식 $f\_1,\backslash ldots,\; f\_k$에 대해 포화를 수행하거나, 곱 $f\; =\; f\_1\; \backslash cdots\; f\_k$인 단일 다항식에 대해 포화를 수행하려는 경우, 동일한 결과를 제공하지만 계산 시간이 매우 다를 수 있는 세 가지 방법이 있다(어떤 방법이 가장 효율적인지는 문제에 따라 다르다).

• 단일 그뢰브너 기저 계산에서 $f\; =\; f\_1\; \backslash cdots\; f\_k$로 포화.
• $f\_1$으로 포화한 다음, 그 결과를 $f\_2$로 포화하는 것을 반복.
• ''F'' 또는 그 그뢰브너 기저에 다항식 $1-t\_1f\_1,\; \backslash ldots,\; 1-t\_kf\_k,$를 추가하고, 단일 그뢰브너 기저 계산에서 $t\_i$를 제거.

7. 1. 아이디얼 멤버십 문제

7. 2. 다항식 방정식계 풀이

7. 3. 소거 이론 (Elimination Theory)

7. 4. 아이디얼의 교집합

7. 5. 유리 곡선의 음함수화 (Implicitization)

7. 6. 포화 (Saturation)

• 단일 그뢰브너 기저 계산에서 $f\; =\; f\_1\; \backslash cdots\; f\_k$로 포화.
• $f\_1$으로 포화한 다음, 그 결과를 $f\_2$로 포화하는 것을 반복.
• ''F'' 또는 그 그뢰브너 기저에 다항식 $1-t\_1f\_1,\; \backslash ldots,\; 1-t\_kf\_k,$를 추가하고, 단일 그뢰브너 기저 계산에서 $t\_i$를 제거.

7. 7. 힐베르트 영점 정리 (Hilbert's Nullstellensatz)

7. 8. 고차원에서의 음함수화

7. 9. 오류 정정 부호 (Error-Correcting Codes)

8. 구현 및 복잡도

부흐베르거 알고리즘은 그뢰브너 기저를 계산하는 가장 오래된 알고리즘으로, 브루노 부흐베르거가 개발했다.^[4] 구현이 간단하지만 초기 구현은 사소한 문제만 해결할 수 있었다. 주요 문제는 중간 다항식 크기 증가, 정수 연산, S-다항식 선택, 그리고 대부분의 S-다항식이 0으로 줄어드는 비효율성 등이다.^[4]

이러한 문제 해결을 위해 장-샤를 포제르는 F4 및 F5 알고리즘을 도입했다.^[4] F4 알고리즘은 여러 S-다항식 감소를 선형대수의 행렬 축소로 대체하여 효율성을 높였다. F5 알고리즘은 축소될 행렬 크기를 줄이는 기준을 도입하여 F4를 개선했다. 특히, F5는 모듈러 정수에서 여러 암호 도전을 해결하는 데 사용되었다.^[4]

FGLM 알고리즘은 다른 단항식 순서에 대한 그뢰브너 기저 계산을 위한 기저 변환 알고리즘이다. 0차원 경우에만 작동하며, 희소 행렬의 특성을 고려하지 않아 효율성이 떨어지는 문제가 있었다. 이후 ''희소 FGLM 알고리즘''이 도입되어 이 문제가 해결되었다.^[5]

널리 사용되는 컴퓨터 대수 시스템(CAS)에는 CoCoA, GAP, Macaulay 2, Magma, Maple, Mathematica, SINGULAR, SageMath, SymPy 등이 있으며, 이들은 그뢰브너 기저 계산을 위한 알고리즘을 구현하고 있다. F4 알고리즘은 일반적으로 부흐베르거 알고리즘보다 효율적이다.^[4]

F4 및 (희소) FGLM 알고리즘의 구현은 라이브러리 ''Msolve''에 포함되어 있다.^[6] Msolve는 GitHub에서 사용할 수 있으며, Julia, Maple, SageMath와 인터페이스되어 해당 환경에서 직접 사용할 수 있다.^[6]

그뢰브너 기저 계산의 복잡도는 일반적으로 변수의 개수 ''n''와 입력 다항식의 최대 차수 ''d''의 관점에서 평가된다. 최악의 경우, 복잡도는 ''n''에 대해 이중 지수적으로 증가한다.^[1]

보다 정확하게는, 복잡성은 $d^\{2^n\}$의 다항식으로 상한이 정해진다. 작은 o 표기법을 사용하면, 이는 $d^\{2^\{n+o(n)\}\}$으로 제한된다. 반면에, 차수가 $d^\{2^\{\backslash Omega(n)\}\}$인 다항식을 포함하거나 $d^\{2^\{\backslash Omega(n)\}\}$개의 원소를 포함하는 기약 그뢰브너 기저의 예가 제시되었다. 그뢰브너 기저를 계산하는 모든 알고리즘은 결과를 기록해야 하므로, 이는 복잡성의 하한을 제공한다.

그뢰브너 기저는 EXPSPACE-완전이다.^[7]

8. 1. 구현

8. 2. 복잡도

9. 일반화

그뢰브너 기저의 개념과 알고리즘은 다항식 환 위의 자유 가군의 부분 가군으로 일반화되었다. 실제로, 만약 ''L''이 환 ''R'' 위의 자유 가군이라면, 두 원소의 곱을 0으로 정의함으로써 직합 $R\backslash oplus\; L$을 환으로 간주할 수 있다. 이 환은 $R[e\_1,\; \backslash ldots,\; e\_l]/\backslash left\backslash langle\; \backslash \{e\_ie\_j|1\backslash le\; i\backslash le\; j\backslash le\; l\backslash \}\backslash right\backslash rangle$과 동일시될 수 있는데, 여기서 $e\_1,\; \backslash ldots,\; e\_l$은 ''L''의 기저이다. 이를 통해 $g\_1,\; \backslash ldots,\; g\_k$에 의해 생성된 ''L''의 부분 가군을 $g\_1,\; \backslash ldots,\; g\_k$와 곱 $e\_ie\_j$, $1\backslash le\; i\backslash le\; j\backslash le\; l$에 의해 생성된 $R[e\_1,\; \backslash ldots,\; e\_l]$의 아이디얼과 동일시할 수 있다. 만약 ''R''이 다항식 환이라면, 이는 가군의 그뢰브너 기저의 이론과 알고리즘을 아이디얼의 그뢰브너 기저의 이론과 알고리즘으로 축소시킨다.

그뢰브너 기저의 개념과 알고리즘은 또한 주 아이디얼 환 또는 바일 대수와 같은, 가환적이거나 그렇지 않은 다양한 환 위의 아이디얼로 일반화되었다.

참조

_[1] 학술대회 Computer Algebra
_[2] 저널 Contributions to constructive polynomial ideal theory XXIII: forgotten works of Leningrad mathematician N. M. Gjunter on polynomial ideal theory http://www.risc.jku.[...] 2003-06-01
_[3] 서적 Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra Springer
_[4] 저널 Converting bases with the Gröbner walk Elsevier
_[5] 저널 Sparse FGLM algorithms Elsevier
_[6] 학술대회 Msolve: a library for solving polynomial systems https://hal.sorbonne[...]
_[7] 저널 Some Complexity Results for Polynomial Ideals 1997-09-01
_[8] 저널 Use of Gröbner bases to decode binary cyclic codes up to the true minimum distance https://ieeexplore.i[...]
_[9] 저널 Decoding affine variety codes using Gröbner bases
_[10] 서적 Gröbner Bases, Coding, and Cryptography Springer
_[11] 웹사이트 Groebner Bases: A Short Introduction for Systems Theorists http://www.risc.uni-[...] Proceedings of EUROCAST 2001
_[12] 웹사이트 Gröbner Basis Theory http://www.cs.le.ac.[...] Leicester University 2001-01-01
_[13] 웹사이트 実際の計算 http://aleph.sagemat[...]
_[14] 논문 Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal http://www.risc.jku.[...] 인스브루크 대학교 1965-01-01
_[15] 저널 Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems 1970-10-01